/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.vijos;

import java.util.ArrayList;
import java.util.List;

/**
 *
 *@author : sunzb(sunzb@hsit.com.cn)
 *@date: 2019/4/23
 */
//求二叉树的先序序列
//第一行为二叉树的中序序列 左根右
//第二行为二叉树的后序序列 左右根
//输出:一行，为二叉树的先序序列 根左右
public class P11_1_1132 {

    public static String test(String zx, String hx) {
        TreeNode root = buildTree(zx.toCharArray(), hx.toCharArray(), null, true);
        StringBuilder result = new StringBuilder();
        // 中序
        zx(root, result);
        System.out.println("zx:" + result);
        result = new StringBuilder();
        // 后序
        hx(root, result);
        System.out.println("hx:" + result);
        result = new StringBuilder();
        // 前序
        qx(root, result);
        return result.toString();
    }

    private static void qx(TreeNode root, StringBuilder result) {
        result.append(root.getValue());
        if (root.getLeft() != null) {
            qx(root.getLeft(), result);
        }
        if (root.getRight() != null) {
            qx(root.getRight(), result);
        }
    }

    private static void zx(TreeNode root, StringBuilder result) {
        if (root.getLeft() != null) {
            zx(root.getLeft(), result);
        }
        result.append(root.getValue());
        if (root.getRight() != null) {
            zx(root.getRight(), result);
        }
    }

    private static void hx(TreeNode root, StringBuilder result) {
        if (root.getLeft() != null) {
            hx(root.getLeft(), result);
        }
        if (root.getRight() != null) {
            hx(root.getRight(), result);
        }
        result.append(root.getValue());
    }

    public static TreeNode buildTree(char[] zxChars, char[] hxChars, TreeNode parent, boolean isLeft) {
        int length = zxChars.length;
        TreeNode root = new TreeNode(hxChars[length - 1], parent, isLeft);
        if (length == 1) {
            return root;
        }
        StringBuilder leftSb = new StringBuilder();
        StringBuilder rightSb = new StringBuilder();
        boolean left = true;
        for (Character c : zxChars) {
            if (c.equals(root.value)) {
                left = false;
                continue;
            }
            if (left) {
                leftSb.append(c);
            } else {
                rightSb.append(c);
            }
        }
        if (leftSb.length() > 0) {
            char[] newZxChars = leftSb.toString().toCharArray();
            buildTree(newZxChars, newHx(newZxChars, hxChars), root, true);
        }
        if (rightSb.length() > 0) {
            char[] newZxChars = rightSb.toString().toCharArray();
            buildTree(newZxChars, newHx(newZxChars, hxChars), root, false);
        }
        return root;
    }

    private static char[] newHx(char[] zxChars, char[] hxChars) {
        StringBuilder sb = new StringBuilder();
        for (Character hx : hxChars) {
            boolean find = false;
            for (char zx : zxChars) {
                if (hx.equals(zx)) {
                    find = true;
                }
            }
            if (find) {
                sb.append(hx);
            }
        }
        return sb.toString().toCharArray();
    }

    public static class TreeNode {
        private TreeNode parent;
        private char value;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(char value, TreeNode parent, boolean isLeft) {
            this.value = value;
            this.parent = parent;
            if (parent != null) {
                if (isLeft) {
                    parent.left = this;
                } else {
                    parent.right = this;
                }
            }
        }

        public TreeNode getParent() {
            return parent;
        }

        public TreeNode setParent(TreeNode parent) {
            this.parent = parent;
            return this;
        }

        public char getValue() {
            return value;
        }

        public TreeNode setValue(char value) {
            this.value = value;
            return this;
        }

        public TreeNode getLeft() {
            return left;
        }

        public TreeNode setLeft(TreeNode left) {
            this.left = left;
            return this;
        }

        public TreeNode getRight() {
            return right;
        }

        public TreeNode setRight(TreeNode right) {
            this.right = right;
            return this;
        }
    }

    public static void main(String[] args) {
        System.out.println(test("BADC", "BDCA").equals("ABCD"));
//        1  2  4  5  7  8  3  6
        System.out.println(test("42758136", "47852631"));
    }
}
